/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 晓星航
 * Date: 2023-11-14
 * Time: 10:40
 */
public class MaxSubarraySum {
    public static void main(String[] args) {
        int[] arr = {1, -2, 3, 5, -3, 2};
        int maxSum = maxSubarraySum(arr, 0, arr.length - 1);
        System.out.println("Max subarray sum: " + maxSum);
    }

    static int maxSubarraySum(int[] arr, int low, int high) {
        if (low == high) {
            return arr[low];
        }
        int mid = (low + high) / 2;
        int leftMax = maxSubarraySum(arr, low, mid);
        int rightMax = maxSubarraySum(arr, mid + 1, high);
        int crossMax = maxCrossingSum(arr, low, mid, high);
        return Math.max(Math.max(leftMax, rightMax), crossMax);
    }

    static int maxCrossingSum(int[] arr, int low, int mid, int high) {
        int leftSum = Integer.MIN_VALUE;
        int rightSum = Integer.MIN_VALUE;
        int sum = 0;
        for (int i = mid; i >= low; i--) {
            sum += arr[i];
            if (sum > leftSum) {
                leftSum = sum;
            }
        }
        sum = 0;
        for (int i = mid + 1; i <= high; i++) {
            sum += arr[i];
            if (sum > rightSum) {
                rightSum = sum;
            }
        }
        return leftSum + rightSum;
    }
}
